/**
 * 
 */
package leetCode;

import java.util.HashSet;

/**
 * @author zhongfang
 *
 */
public class TwoSumIV {
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public boolean findTarget2(TreeNode root, int k) {
		return dfs(root,root,k);
	}

	private boolean dfs(TreeNode from, TreeNode cur, int k) {
		if(cur==null)
			return false;
		int otherVal=k-cur.val;
		return search(from, cur, otherVal)//在整棵树中找另一个节点
				||dfs(from, cur.left, k)||dfs(from, cur.right, k);// 为左右子树的所有节点在整棵树中找另一个节点
	}

	private boolean search(TreeNode root, TreeNode beforeNode, int otherVal) {
		if (root == null)
			return false;
		if (root.val == otherVal&&root!=beforeNode) {
			return true;
		} else if (root.val < otherVal) {
			return search(root.right, beforeNode, otherVal);
		} else {
			return search(root.left, beforeNode, otherVal);
		}
	}

	public boolean findTarget(TreeNode root, int k) {
		return help(root, new HashSet<Integer>(), k);
	}

	private boolean help(TreeNode root, HashSet<Integer> hashSet, int k) {
		if (root == null) {
			return false;
		}
		if (hashSet.contains(k - root.val)) {
			return true;
		}
		hashSet.add(root.val);
		return help(root.left, hashSet, k) || help(root.right, hashSet, k);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
